package chapter_04;

// 循环队列
/*
队列的效率
和栈一样，队列插入数据和移除数据项的时间复杂均为O(1)。

双端队列
双端队列就是一个两端都是结尾的队列。队列的每一端都可以插入数据项和移除数据项。这些方法可以叫做
insertLeft()和insertRight()，以及removeLeft()和removeRight()。
 */


public class Queue {
    private int maxSize;
    private long[] queArray;
    private int front;    // 队首索引
    private int rear;     // 队尾索引
    private int nItems;   // 当前队列里数据项的个数

    public Queue(int s) {
        maxSize = s;
        queArray = new long[maxSize];
        front = 0;      // head
        rear = -1;      // 队尾
        nItems = 0;     // 元素个数
    }

    public void insert(long j) {
        // 当队列已经满了的时候，回到队首，覆盖掉第一个
        if (rear == maxSize - 1)
            rear = -1;
        queArray[++rear] = j;
        nItems++;
    }

    public long remove() {
        // 每删除一次，队头就自增一次，当增加到队尾的时候，又倒回去
        long temp = queArray[front++];
        if (front == maxSize)
            front = 0;
        nItems--;
        return temp;
    }

    public long peekFront() {
        return queArray[front];
    }

    public boolean isEmpty() {
        return nItems == 0;
    }

    public boolean isFull() {
        return nItems == maxSize;
    }

    public int size() {
        return nItems;
    }
}


class QueueApp {

    public static void main(String[] args) {
        Queue theQueue = new Queue(5);
        theQueue.insert(10);
        theQueue.insert(20);
        theQueue.insert(30);
        theQueue.insert(40);

        theQueue.remove();
        theQueue.remove();
        theQueue.remove();

        theQueue.insert(50);
        theQueue.insert(60);
        theQueue.insert(70);
        theQueue.insert(80);

        while (!theQueue.isEmpty()) {
            long n = theQueue.remove();
            System.out.print(n + " ");
        }
    }
}
